/*
	Name: 
	Copyright: 
	Author: Karamen
	Date: 21/03/14 12:31
	Description: Mo phong thuat toan MergeSort
*/

#include <conio.h>
#include <stdio.h>
#include <math.h>

// ------- Tron hai day thanh 1 day
void Merge(int arr[],int min,int mid,int max)
{
  int tmp[30];
  int i,j,k,m; 
  j=min;
  m=mid+1;
  for(i=min; j<=mid && m<=max ; i++)
  {
     if(arr[j]<=arr[m])
     {
         tmp[i]=arr[j];
         j++;
     }
     else
     {
         tmp[i]=arr[m];
         m++;
     }
  }
  if(j>mid)
  {
     for(k=m; k<=max; k++)
     {
         tmp[i]=arr[k];
         i++;
     }
  }
  else
  {
     for(k=j; k<=mid; k++)
     {
        tmp[i]=arr[k];
        i++;
     }
  }
  for(k=min; k<=max; k++)
     arr[k]=tmp[k];
}

void MergeSort(int arr[], int min, int max){
	int mid;
	 if(min<max)
	 {
	   mid=(min+max)/2;
	   MergeSort(arr,min,mid);
	   MergeSort(arr,mid+1,max);
	   Merge(arr,min,mid,max);
	 }
}

void xuatMang(int a[], int n){
	for(int i = 0; i< n; i++){
		printf("\t %d",a[i]);
	}
}
void nhapMang(int a[], int n){
		printf("\nNhap cac phan tu mang: \n");
		for(int i = 0; i < n ; i++){
			printf("A[%d]=",i);
			scanf("%d",&a[i]);
		}
}
int main(){
	int array[50],n;
	printf("Nhap vao kich thuoc mang: ");
	scanf("%d",&n);
	nhapMang(array, n);
	printf("\n Mang vua nhap vao la: \n");
	xuatMang(array,n);
	printf("\n Mang Sau khi sap xep theo MergeSort :\n");
	MergeSort(array,0,n-1);
	xuatMang(array,n);
	getch();
}
